package medium;

import java.util.HashMap;

public class T3291 {

    public static void main(String[] args) {
        String[] words = {"abababab", "ab"};
        String target = "ababaababa";
        System.out.println(minValidStrings(words, target));
    }

    static HashMap<String, Integer> wordMaxPrefix;

    public static int minValidStrings(String[] words, String target) {
        wordMaxPrefix = new HashMap<>();
        int[] dpArr = new int[target.length() + 1];

        int maxValidLen = 0;
        int jumpCount = 1;
        int i = 0, j = 0;
        // i重置为j的位置继续循环
        do {
            // 例如 2 3 1 1 1 1，dpArr[i]能到达下标i+1，与i+2的位置
            // 到达i+1组成的和是dpArr[i+1]+dpArr[i]-1=4，到达i+2组成的和是dpArr[i+2]+dpArr[i]=3
            // 设dpArr[i]能达到下标i+1~i+k的位置
            // 那么到达i+k组成的和是dpArr[i+k]+dpArr[i]-(dpArr[i]-k))) = dpArr[i+k]+k
            int maxJump = Integer.MIN_VALUE;
            boolean haveMaxJump = false;
            if (dpArr[i] == 0) {
                dpArr[i] = dp(i, words, target);
            }
            if (dpArr[0] >= target.length()) {
                return 1;
            }
            // 找出dpArr[i]能到的所有下标中，组成的和的最大值的下标。
            for (int k = 1; k <= dpArr[i]; k++) {
                // i到i+k的值
                if (dpArr[i + k] == 0) {
                    dpArr[i + k] = dp(i + k, words, target);
                }
                int dpIJ = dpArr[i + k] + k;
                if (dpIJ >= maxJump) {
                    maxJump = dpIJ;
                    haveMaxJump = true;
                    j = i + k;
                }
            }
            // 跳到目的地下标
            if (haveMaxJump) {
                if (dpArr.length == 2 || words.length == 1) {
                    if (dpArr[0] > 0) {
                        return 1;
                    } else {
                        return -1;
                    }
                }
                jumpCount++;
                maxValidLen += maxJump;
                if (i != 0) {
                    maxValidLen -= dpArr[i];
                }
                i = j;
            } else {
                return -1;
            }

        } while (maxValidLen < target.length());

        return jumpCount;
    }

    /**
     * dp[i]表示从target[i]起最长的前缀
     * 例如 words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
     * dp[0] = 2， 因为 target[0]起的前缀aa，与words[1]的aa匹配
     * dp[1] = 3， 因为 target[1]起的前缀abc，与words[0]的abc匹配
     */
    public static int dp(int i, String[] words, String target) {
        String targetSub = target.substring(i);
        int maxPrefixLen = -1;
        for (String word : words) {
            int prefixLen = maxPrefix(word, targetSub);
            if (prefixLen > maxPrefixLen) {
                maxPrefixLen = prefixLen;
            }
        }
        return maxPrefixLen;
    }

    /**
     * 最长匹配字串 KMP
     */
    public static int maxPrefix(String word, String target) {
        if (wordMaxPrefix.containsKey(word + "-" + target)) {
            return wordMaxPrefix.get(word + "-" + target);
        }

        int i = 0;
        while (true) {
            if (word.length() <= i || i >= target.length()) {
                if (i == 0) {
                    wordMaxPrefix.put(word + "-" + target, -1);
                    return -1;
                } else {
                    wordMaxPrefix.put(word.substring(0, i) + "-" + target, i);
                    return i;
                }
            } else {
                if (word.charAt(i) != target.charAt(i)) {
                    if (i == 0) {
                        wordMaxPrefix.put(word + "-" + target, -1);
                        return -1;
                    } else {
                        wordMaxPrefix.put(word.substring(0, i) + "-" + target, i);
                        return i;
                    }

                }
            }
            i++;
        }
    }
}

